// 哈希表可以提供非常快速的 插入 删除 查找操作
// 实现Hash函数

const hashFn = (string, limit = 7) => {
  let hash = 0;
  for (const item of string) {
    hash = ((hash << 5) - hash) + item.charCodeAt()
  }
  return hash % limit;
}
// 创建hashTable类
class HashTable {
  constructor () {
    this.storage = [] // 哈希表存储数据的变量
    this.count = 0 // 当前存放的元素个数
    this.limit = 7 // 哈希表长度
    // 装填因子(已有个数/总个数)
    this.loadFactor = 0.75;
    this.minLoadFactor = 0.25;
  }
  put (key, value) {
    // 1.根据key 获取映射到storage里面的index
    const index = hashFn(key, this.limit)
    // 2.根据index取出storage中的值
    let bucket = this.storage[index]
    // 3.判断bucket是否存在
    if (bucket === undefined) {
      // 说明哈希表中没有
      bucket = []
      this.storage[index] = bucket
    }
    // 修改数据
    for (let i = 0; i < bucket.length; i++) {
      let tuple = bucket[i]
      if (tuple[0] === key) {
        // key 相等则修改数据
        tuple[1] = value
        return
      }
    }
    // 5. 新增数据
    bucket.push([key, value])
    this.count++
    //  6. 判断哈希表是否需要扩容 若装填因子>0.75 则扩容
    if (this.count / this.limit > this.loadFactor) {
      this.resize(this.getPrime(this.limit * 2))
    }
  }
  // getPrime(number) 根据传入的number 获取最邻近的质数
  getPrime (number) {
    while (!isPrime(number)) {
      number++
    }
    return number
  }
  // 重新跳转哈希表的大小 扩容或压缩
  resize (newLimit) {
    // 1. 保存旧的storage 数字内容
    const oldStorage = this.storage
    // 2. 重置所有的属性
    this.storage = []
    this.limit = newLimit
    this.count = 0
    for (const item of oldStorage) {
      if (item) {
        for (const b of item) {
          this.put(b[0], b[1])
        }
      }
    }
  }
  // 根据key 获取value
  get (key) {
    // 1.首先计算出key 的值
    let index = hashFn(key, this.limit)
    const bucket = this.storage[index]
    if (bucket === undefined) {
      return false
    }
    for (const tuple of bucket) {
      if (tuple[0] === key) {
        return tuple[1]
      }
    }
    return null
  }
  // 根据key,删除指定key的数据
  remove (key) {
    // 1. 根据hash函数计算当前key的哈希值
    let index = hashFn(key, this.limit)
    let bucket = this.storage[index]
    console.log(bucket, '===============');
    if (bucket === undefined) {
      return null
    }
    for (let i = 0, len = bucket.length; i < len; i++) {
      const tuple = bucket[i]
      if (tuple[0] === key) {
        bucket.splice(i, 1)
        this.count--
        if (this.limit > 7 && this.count / this.limit < this.minLoadFactor) {
          this.resize(this.getPrime(Math.floor(this.limit / 2)));
        }
        return tuple;
      }
    }
  }
  isEmpty () {
    return this.count === 0
  }
  size () {
    return this.count
  }
}
// 判断一个数是否为质数
function isPrime (numebr) {
  if (number <= 1 || number === 4) {
    return false
  }
  const tmp = Math.ceil(Math.sqrt(number))
  for (let i = 2; i < tmp; i++) {
    if (number % 2 === 0) {
      return false
    }
  }
}
const hashTable = new HashTable();
hashTable.put('name', 'XPoet');
hashTable.put('age', 18);
hashTable.put('height', 178);
hashTable.put('email', 'i@xpoet.cn');
hashTable.put('address', 'china');
//{"storage":[[["height",178]],[["name","XPoet"]],[["age",18],["email","i@xpoet.cn"],["address","china"]]],"count":5,"limit":7,"loadFactor":0.75,"minLoadFactor":0.25}
// console.log(JSON.stringify(hashTable));
// console.log(hashTable.get('name'));
console.log(hashTable.remove('email'));
console.log(JSON.stringify(hashTable));
